import java.util.Arrays;

public class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        if(n == 1){
            return;
        }
        if(n == 2){
            swap(nums,0,1);
            return;
        }
        for(int i = n-2; i >= 0; i--){
            if(nums[i] < nums[i+1]){
                for (int j = n-1; j >= 0; j--) {
                    if(nums[j] > nums[i]) {
                        swap(nums,i,j);
                        reverse(nums, i+1);
                        return;
                    }
                }

            }
        }
        Arrays.sort(nums);
    }
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

}
